We say that $f(n)$ is $O(g(n))$ if there is a real contant $c > 0$ and an integer constant $n_0 >= 1$ such that:
$$f(n) <= cg(n), \quad for \quad n >= n_0$$
In [8]:
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
print(fact(3))
In [20]:
def BinarySearch(myList, val, low, high):
mid = (low + high)//2 #this tripped me up. Can we low + (high-low)//2?
if low > high:
return False
if myList[mid] == val:
return True
elif val < myList[mid]:
return BinarySearch(myList, val, low, mid-1)
else:
return BinarySearch(myList, val, mid+1, high)
myList = [1,2,3, 10, 20, 35]
BinarySearch(myList, 35, 0, len(myList)-1)
Out[20]:
In [44]:
def reverse(S, start, stop):
if start < stop - 1:
S[start],S[stop-1] = S[stop-1],S[start]
reverse(S, start+1, stop-1)
s = [1,2,3,4,5]
reverse(s,0,len(s))
print(s)
In [52]:
import math
def ireverse(S, start, stop):
swaps = math.ceil((stop - start)/2)
for x in range(swaps):
swap(s, start+x, stop-x)
def swap(s, index1, index2):
temp = s[index1]
s[index1] = s[index2]
s[index2] = temp
s=[1,2,3,4,5,6]
ireverse(s,0,len(s)-1)
print(s)
ireverse(s,2,5)
print(s)
In [ ]: